#include <iostream>
#include <vector>

using namespace std;

int partitionHoare(vector<int> &arr,int low,int high){
    int pivot=arr[low+(high-low)/2];
    int i=low-1;
    int j=high+1;
    while(true){
        do{
            ++i;
        }while(arr[i]>pivot);
        do{
            --j;
        }while(arr[j]<pivot);

        if(i>=j){
            return j;
        }
        swap(arr[i],arr[j]);
    }
}

void quickSortHoare(vector<int> &arr,int low,int high){
    int pivotIndex=partitionHoare(arr,low,high);
    quickSortHoare(arr,low,pivotIndex);
    quickSortHoare(arr,pivotIndex+1,high);
}

void test(){
    vector<int> arr={8,5,1,3,9,2,4};
    quickSortHoare(arr,0,arr.size()-1);
    for(auto &elem : arr){
        cout << elem << " ";
    }
    cout << endl;
}

int main()
{
    test();
    return 0;
}

